package com.demo.java.OD251_300.OD262;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【超级玛丽过吊桥】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146059249
 */
public class OdMain {
    // 动态规划求解的主函数
    public static int solve(int M, int N, int K, int[] trap) {
        // 初始化桥梁的状态，true表示没有陷阱，false表示有陷阱
        boolean[] bridge = new boolean[N + 2];  // 使用N+2是为了避免边界溢出
        Arrays.fill(bridge, true);  // 全部设置为true，表示没有陷阱
        for (int i : trap) {
            bridge[i] = false;  // 对应的位置上设为false，表示有陷阱
        }

        // 初始化dp数组，dp[i][j]表示从位置i到达j的路径数
        int[][] dp = new int[N + 2][M + 2];
        dp[0][M] = 1;  // 起始位置设置为1条路径

        // 递推关系
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length - 1; j++) {
                // 判断当前位置是否能通过
                int k = bridge[i] ? j : j + 1;
                // 根据不同步数的递推关系更新dp值
                dp[i][j] = (i == 1) ? dp[i - 1][k] :
                        ((i == 2) ? dp[i - 1][k] + dp[i - 2][k] :
                                dp[i - 1][k] + dp[i - 2][k] + dp[i - 3][k]);
            }
        }

        // 计算最终结果，路径数累加
        int res = 0;
        for (int i = 0; i < dp[0].length - 1; i++) {
            res += dp[N + 1][i];
        }
        return res;
    }

    // 主函数，获取输入并调用求解函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();  // 木板总数
        int N = sc.nextInt();  // 陷阱的数量
        int K = sc.nextInt();  // 陷阱的位置数量
        if (M <= 0 || M > 1000 || N <= 0 || N > 1000 || K <= 0 || K > 1000) {
            System.out.println("Invalid input");
            return;
        }
        int[] trap = new int[K];
        for (int i = 0; i < K; i++) {
            trap[i] = sc.nextInt();  // 输入陷阱的具体位置
        }
        System.out.println(solve(M, N, K, trap));  // 输出结果
    }
}